package leetcode_core.dataStruct;

public class MaxPQ <Key extends Comparable<Key>>{//Key可以是任何一种可比较大小的数据类型,比如Integer等
    //存储元素的数组
    private Key[] pq;
    //当前PQ中的元素个数
    private int size = 0;

    public MaxPQ(int cap){
        //索引0是为了来应对根节点寻找父节点的情况的,所以多分配一个内存空间,key extends<key>,属于一个向上转型
        pq = (Key[]) new Comparable[cap+1];
    }

    /*返回当前队列中的最大元素*/
    public Key max(){
        return pq[1];
    }

    /*插入元素e*/
    public void insert(Key e){
        this.size++;
        //先把新元素加到最后
        pq[this.size] = e;
        //然后让它上浮到正确的位置
        this.swim(size);
    }

    //删除并返回当前队列元素中的最大元素
    public Key deleteMax(){
        // 最大堆的堆顶就是最大元素
        Key max = pq[1];
        // 把这最大元素换到最后,删除之
        this.swap(1,size);
        pq[size] = null;
        this.size--;
        //让 pq[1]下沉到正确的位置
        sink(1);
        return max;
    }



    //上浮第x个元素,以维护最大堆的性质
    private void swim(int x){
        //如果浮到堆顶,就不能再上浮了
        while (x>1 && less(parent(x),x)){
            // 如果第x个元素比上层
            //那么就将x换上去
            swap(parent(x),x);
            x=parent(x);
        }
    }

    //下沉第x个元素,以维护最大堆的性质
    private void sink(int x){
        //如果沉到堆底,那么就沉不下去了
        while (left(x) <= size){
            //先假设左边节点比较大
            int max = left(x);
            //如果右边节点存在,比一下大小
            if(right(x) <= size && less(max,right(x))){
                max = right(x);
            }
            //节点x比两孩子都大,就不必下沉了
            if(less(max,x)){
                break;
            }
            //否则不符合最大堆的结构,下沉x节点
            swap(x,max);
            x = max;
        }
    }

    //交换数组的两个元素
    private void swap(int i ,int j){
        Key temp = pq[i];
        pq[i] = pq[j];
        pq[j] = temp;
    }

    //pq[i]是否比pq[j]要小
    private boolean less(int i,int j){
        return pq[i].compareTo(pq[j]) < 0 ;//如果pq[i] - pq[j] <0那么返回true
    }

    //父节点的索引
    private int parent(int root){
        return root/2;
    }
    //左孩子的索引
    private int left(int root){
        return root*2;
    }
    //右孩子的索引
    private int right(int root){
        return left(root)+1;//root*2+1
    }



}
